package org.hot100.h075;

/**
 * @Author: wjy
 * @Date: 2021/12/27 10:59
 */
public class Solution {

    public static void main(String[] args) {

        int[] ints = {2, 0, 2, 1, 1, 0};

        Solution solution = new Solution();
        solution.sortColors(ints);

    }

    public void sortColors(int[] nums) {
        if (nums.length == 0) {
            return;
        }
        this.quickSort(nums, 0, nums.length - 1);

    }

    public void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int l = left, r = right;

        while (l < r) {
            while (l < r && nums[r] >= nums[left]) {
                r--;
            }
            while (l < r && nums[l] <= nums[left]) {
                l++;
            }
            this.swap(nums, l, r);
        }
        this.swap(nums, l, r);
        this.quickSort(nums, left, l - 1);
        this.quickSort(nums, l + 1, right);
    }

    public void swap(int[] nums, int l, int r) {
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] = temp;
    }

}
